package com.azure.code.dfs;

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.stream.Stream;

import static java.util.Comparator.reverseOrder;

/**
 * 划分为k个相等的子集
 */
public class PartitionKSumSubsets_698 {


    /**
     *  视角一： 以nums数字为视角，每个数字都要选择进入到k个桶的某一个
     */
    boolean canPartitionSubSets(int[] nums,int k){
        // 排除一些基本情况
        if(k > nums.length) return false;
        int sum = 0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum % k != 0) return false;

        // k 个桶(集合),记录每个桶装的数字和
        int[] bucket = new int[k];
        // 理论上每个桶中的数字和
        int target = sum / k;
        return  backTrack(nums,0,bucket,target);
    }

    private boolean backTrack(int[] nums, int index, int[] bucket, int target) {
         if(index == nums.length){
             // 检查所有的桶的数字之和是否都是target
             for (int b : bucket) {
                 if(b!=target){
                     return false;
                 }
             }
             // num 成功平分成 k 个子集
             return  true;
         }
        // 穷举 nums[index] 可能装入的桶
        for (int i = 0; i < bucket.length; i++) {
            // 剪枝，桶装满了
            if(bucket[i] + nums[index] > target){
                continue;
            }
            // 将nums[index]装入 bucket[i]
            bucket[i] += nums[index];
            if(backTrack(nums,index+1,bucket,target)){
                return true;
            }
            bucket[i] -= nums[index];
        }
        // nums[index] 装入那个桶都不行
        return false;
    }

    /**
     *  视角二，以k个桶为视角，对于每个桶，都要遍历nums中的n个数字，然后选择是否
     *  将当前遍历的数字装进自己这个桶中
     */
    boolean canPartitionSubSets2(int[] nums,int k){
        // 排除一些基本情况
        if (k > nums.length) return false;
        int sum = 0;
        for (int v : nums) sum += v;
        if (sum % k != 0) return false;
        int target = sum/k;
        boolean[] used = new boolean[nums.length];
//        while (k>0){
//            int bucket = 0;
//            for(int i = 0; i< nums.length;i++){
//                // 决定是否将nums[i] 放入到当前桶中
//                if(!used[i]&&canAdd(bucket,nums[i])){ 这个很难弄
//
//                    bucket+=nums[i];
//                    used[i] = true;
//                }
//                if(bucket==target){
//                    // 装满了一个桶，装下一个桶
//                    k--;
//                    break;
//                }
//            }
//        }
        // k 号桶初始什么都没有装，从nums[0]开始做选择
        return  backTrack2(k,0,nums,0,used,target);
    }

    private boolean canAdd(int bucket, int num) {
        if(num==bucket) return true;
        return true;
    }
    // k 号桶 初始什么都没有安装，从nums[0]开始做选择
    private boolean  backTrack2(int k,int bucket,int[] nums,int start,
                             boolean[] used,int target){
        // base case
        if(k==0){
            // 所有的桶都被装满了，而且 nums 一定全部用完了
            // 因为 target == sum / k
            return true;
        }
        if(bucket==target){
            // 装满了当前桶，递归穷举下个桶的选择
            // 让下个桶从 num[0]开始选数字
            return backTrack2(k-1,0,nums,0,used,target);
        }

        // 从start 开始向后探视有效的nums[i] 装入当前桶
        for(int i = start; i < nums.length;i++){
            // 剪枝
            if(used[i]){
                continue;
            }
            if(nums[i]+bucket>target){
                // 当前桶安装不下 nums[i]
                continue;
            }
            used[i] = true;
            bucket+=nums[i];
            if(backTrack2(k,bucket,nums,i+1,used,target)){
                return true;
            }
            used[i] = false;
            bucket-=nums[i];
        }
        return false;
    }

}
